#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 60906 2021/2/2

class Solution10(object):
    def numSimilarGroups(self, strs):
        """
        高! 以字符串所在索引作为该字符串的id, 用此id来计算连通分量. 节省很多空间.

        :type strs: List[str]
        :rtype: int
        """
        N = len(strs)
        dsu = DSU(N)
        # 两两对比判断连通性(相似)
        for i in range(N):
            for j in range(i + 1, N):
                if self.isSimilar(strs[i], strs[j]):
                    dsu.union(i, j)
        return dsu.regions()

    def isSimilar(self, str1, str2):
        count = 0
        for i in range(len(str1)):
            if str1[i] != str2[i]:
                count += 1
        return count == 2 or count == 0

class DSU:
    def __init__(self, N):
        self.par_ = range(N + 1)
        # 初始 N 个节点, 就是 N 个分量
        self.regions_ = N

    def find(self, x):
        if x != self.par_[x]:
            # 高! 路径上所有节点都改为直接指向根节点. 这样下次 find 效率瞬间提升
            self.par_[x] = self.find(self.par_[x])
        return self.par_[x]

    # x,y 在一棵树上, 什么也不用做; 否则, 归并两颗树
    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        self.par_[px] = py
        self.regions_ -= 1

    def regions(self):
        return self.regions_


if __name__ == '__main__':
    # strs = ["tars", "rats", "arts", "star"]
    # strs = ["kccomwcgcs", "socgcmcwkc", "sgckwcmcoc", "coswcmcgkc", "cowkccmsgc", "cosgmccwkc", "sgmkwcccoc", "coswmccgkc", "kowcccmsgc", "kgcomwcccs"]
    # strs = ["blw","bwl","wlb"]
    strs = ["qihcochwmglyiggvsqqfgjjxu","gcgqxiysqfqugmjgwclhjhovi","gjhoggxvcqlcsyifmqgqujwhi","wqoijxciuqlyghcvjhgsqfmgg","qshcoghwmglygqgviiqfjcjxu","jgcxqfqhuyimjglgihvcqsgow","qshcoghwmggylqgviiqfjcjxu","wcoijxqiuqlyghcvjhgsqgmgf","qshcoghwmglyiqgvigqfjcjxu","qgsjggjuiyihlqcxfovchqmwg","wcoijxjiuqlyghcvqhgsqgmgf","sijgumvhqwqioclcggxgyhfjq","lhogcgfqqihjuqsyicxgwmvgj","ijhoggxvcqlcsygfmqgqujwhi","qshcojhwmglyiqgvigqfgcjxu","wcoijxqiuqlyghcvjhgsqfmgg","qshcojhwmglyiggviqqfgcjxu","lhogcgqqfihjuqsyicxgwmvgj","xscjjyfiuglqigmgqwqghcvho","lhggcgfqqihjuqsyicxgwmvoj","lhgocgfqqihjuqsyicxgwmvgj","qihcojhwmglyiggvsqqfgcjxu","ojjycmqshgglwicfqguxvihgq","sijvumghqwqioclcggxgyhfjq","gglhhifwvqgqcoyumcgjjisqx"]
    c = Solution10().numSimilarGroups(strs)
    print("count: " + str(c))
